#include<iostream>
using namespace std;
void gg(int a,int b,int &x,int &y){
	if(!b){
		x=1,y=0;
		return;
	}
	gg(b,a%b,x,y);
	int k=x;x=y;
    y=k-a/b*y;
}
int a,b,x,y;
int main(){
	cin>>a>>b;
	gg(a,b,x,y);
	cout<<(x+b)%b<<endl;
	return 0;
}
